package com.gitee.wsl.func.filter.bloomfilter.hasher

import com.gitee.wsl.func.filter.bloomfilter.bean.BitMaps.mod
import com.gitee.wsl.func.filter.bloomfilter.api.Hasher
import com.gitee.wsl.func.filter.bloomfilter.api.IndexExtractor
import com.gitee.wsl.func.filter.bloomfilter.bean.Shape
import com.gitee.wsl.func.predicate.IntPredicate
import com.gitee.wsl.func.predicate.Predicate
import kotlin.math.min


/**
 * A Hasher that implements combinatorial hashing as described by
 * [Krisch and Mitzenmacher](https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf) using the enhanced double hashing technique
 * described in the wikipedia article  [Double Hashing](https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing).
 *
 *
 * Common use for this hasher is to generate bit indices from a byte array output of a hashing
 * or MessageDigest algorithm.
 *
 * <h2>Thoughts on the hasher input</h2>
 *
 *
 * Note that it is worse to create smaller numbers for the `initial` and `increment`. If the `initial` is smaller than
 * the number of bits in a filter then hashing will start at the same point when the size increases; likewise the `increment` will be
 * the same if it remains smaller than the number of bits in the filter and so the first few indices will be the same if the number of bits
 * changes (but is still larger than the `increment`). In a worse case scenario with small `initial` and `increment` for
 * all items, hashing may not create indices that fill the full region within a much larger filter. Imagine hashers created with `initial`
 * and `increment` values less than 255 with a filter size of 30000 and number of hash functions as 5. Ignoring the
 * tetrahedral addition (a maximum of 20 for k=5) the max index is 255 * 4 + 255 = 1275, this covers 4.25% of the filter. This also
 * ignores the negative wrapping but the behavior is the same, some bits cannot be reached.
 *
 *
 * So this needs to be avoided as the filter probability assumptions will be void. If the `initial` and `increment` are larger
 * than the number of bits then the modulus will create a 'random' position and increment within the size.
 *
 *
 * @since 4.5.0-M1
 */
class EnhancedDoubleHasher : Hasher {
    /**
     * Gets the initial value for the hash calculation.
     *
     * @return the initial value for the hash calculation.
     */
    /**
     * The initial hash value.
     */
    val initial: Long

    /**
     * Gets the increment value for the hash calculation.
     *
     * @return the increment value for the hash calculation.
     */
    /**
     * The value to increment the hash value by.
     */
    val increment: Long

    /**
     * Constructs the EnhancedDoubleHasher from a byte array.
     *
     *
     * This method simplifies the conversion from a Digest or hasher algorithm output
     * to the two values used by the EnhancedDoubleHasher.
     *
     * The byte array is split in 2 and the first 8 bytes of each half are interpreted as a big-endian long value.
     * Excess bytes are ignored.
     * If there are fewer than 16 bytes the following conversions are made.
     *
     *
     *  1. If there is an odd number of bytes the excess byte is assigned to the increment value
     *  1. The bytes allotted are read in big-endian order any byte not populated is set to zero.
     *
     *
     *
     * This ensures that small arrays generate the largest possible increment and initial values.
     *
     *
     * @param buffer the buffer to extract the longs from.
     * @throws IllegalArgumentException is buffer length is zero.
     */
    constructor(buffer: ByteArray) {
        require(buffer.isNotEmpty()) { "buffer length must be greater than 0" }
        // divide by 2
        val segment = buffer.size / 2
        this.initial = toLong(buffer, 0, segment)
        this.increment = toLong(buffer, segment, buffer.size - segment)
    }

    /**
     * Constructs the EnhancedDoubleHasher from 2 longs. The long values will be interpreted as unsigned values.
     *
     * @param initial The initial value for the hasher.
     * @param increment The value to increment the hash by on each iteration.
     */
    constructor(initial: Long, increment: Long) {
        this.initial = initial
        this.increment = increment
    }

    public override fun indices(shape: Shape): IndexExtractor {

        return object : IndexExtractor {
            override fun asIndexArray(): IntArray {
                val result = IntArray(shape.numberOfHashFunctions)
                val idx = IntArray(1)

                // This method needs to return duplicate indices
                processIndices(Predicate { i: Int ->
                    result[idx[0]++] = i
                    true
                })
                return result
            }

            public override fun processIndices(consumer: IntPredicate): Boolean {
                val bits: Int = shape.numberOfBits

                // Enhanced double hashing:
                // hash[i] = ( h1(x) + i*h2(x) + (i*i*i - i)/6 ) mod bits
                // See: https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing
                //
                // Essentially this is computing a wrapped modulus from a start point and an
                // increment and an additional term as a tetrahedral number.
                // You only need two modulus operations before the loop. Within the loop
                // the modulus is handled using the sign bit to detect wrapping to ensure:
                // 0 <= index < bits
                // 0 <= inc < bits
                // The final hash is:
                // hash[i] = ( h1(x) - i*h2(x) - (i*i*i - i)/6 ) wrapped in [0, bits)
                var index = mod(initial, bits)
                if (!consumer.test(index)) {
                    return false
                }
                var inc = mod(increment, bits)

                val k: Int = shape.numberOfHashFunctions

                if (k >= bits) {
                    // the tetraheadral incrementer.  We need to ensure that this
                    // number does not exceed bits-1 or we may end up with an index > bits.
                    var tet = 1
                    for (i in 1..<k) {
                        // Update index and handle wrapping
                        index -= inc
                        index = if (index < 0) index + bits else index
                        if (!consumer.test(index)) {
                            return false
                        }

                        // Incorporate the counter into the increment to create a
                        // tetrahedral number additional term, and handle wrapping.
                        inc -= tet
                        inc = if (inc < 0) inc + bits else inc
                        if (++tet == bits) {
                            tet = 0
                        }
                    }
                } else {
                    for (i in 1..<k) {
                        // Update index and handle wrapping
                        index -= inc
                        index = if (index < 0) index + bits else index
                        if (!consumer.test(index)) {
                            return false
                        }

                        // Incorporate the counter into the increment to create a
                        // tetrahedral number additional term, and handle wrapping.
                        inc -= i
                        inc = if (inc < 0) inc + bits else inc
                    }
                }
                return true
            }
        }
    }

    companion object {
        /**
         * Convert bytes to big-endian long filling with zero bytes as necessary.
         *
         * @param byteArray the byte array to extract the values from.
         * @param offset the offset to start extraction from.
         * @param len the length of the extraction, may be longer than 8.
         * @return
         */
        private fun toLong(byteArray: ByteArray, offset: Int, len: Int): Long {
            var `val`: Long = 0
            var shift: Int = Int.SIZE_BITS
            val end = offset + min(len, Long.SIZE_BYTES)
            for (i in offset..<end) {
                shift -= Byte.SIZE_BITS
                `val` = `val` or ((byteArray[i].toInt() and 0xFF).toLong() shl shift)
            }
            return `val`
        }
    }
}
